问题

    Note:
    Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
    The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    思路

    考虑一下如何将3SUM问题转变一下：如果我们随机确定了一个数a，问题是不是就变成了，在剩下的数里面找到2个数和为0-a，是不是就和2SUM问题一样了？

    其实这题相比2SUM多了几个难点：

    2. 结果要按升序排列

    3. 结果中不能出现重复的结果

    当然，我们可以通过写很多条判断语句解决这些问题，但是其实稍微想一下，可以发现，只要保证数组一开始就有序就好办很多了。

    我们可以选择3个变量，left，mid，right。在循环的时候，永远保证相对顺序就行了。这样在插入结果的时候，就自然是升序的。

    首先，我们考虑如何确定第一个数left，这肯定是我们第一层循环。第一个数可不能无限制的随便选，因为我们要保证上面的几个条件都满足，我们要保证它时刻是最小的数，那么我们可以考虑left取到全部非正数就行了。（如果要和为0，至少要有1个非正数）

    然后就是mid和right的确定了，我们采用思路2的方案，mid和right分别从两端往中央扫描，如果mid+right还比较小，那就需要mid右移，反之right左移

    一切看起来特别美好了，可以当你提交的时候，你会发现，还是会报错，因为它虽然能解决问题2，但是不能处理重复结果。举个最简单的例子：
    -2 -2 -1 -1 0 1 1 2 2
    这个代码会输出数个[-2 0 2] [-1 0 1] ，解决方案也很简单，如果一个left指向的数是之前判断过的，跳过，如果mid和right往中间移动的时候，是刚才的数，也跳过。

    代码